The present invention relates to the digital color image processing arts. It finds particular application in conjunction with color digital image half-toning, and will be described with particular reference thereto. However, it is to be appreciated that the invention is amenable to other applications.
Color in printed digital images results from the combination of a limited set of colors over a small area in densities selected to integrate the desired color response. This is accomplished in many printing devices by reproducing so called "separations" of the image, where each separation provides varying grey values of a single primary color. When the separations are combined together, the result is a full color image.
The particular color of each separation depends on the "color-space" being implemented. Two of the most commonly used color spaces include red-green-blue (RGB) and cyan-magenta-yellow (CMY). The RGB color-space is "additive"--i.e., it uses the addition of select amounts of the primary colors to a black background, with an equal mixture of the three primary colors producing white. In contrast, the CMY color-space is "subtractive"--i.e., the cyan, magenta, and yellow inks remove the primary colors red, green, and blue, respectively, from light reflected off of a white background so that an equal mixture of the three CMY inks produces black due to the absorption of all color.
In practice, color images are often printed in the cyan-magenta-yellow-black (CMYK) color-space. This color-space is based upon the CMY color-space, but attempts to improve the quality of "black" in the image and reduce use of color inks. In theory, images can be printed using the CMY color space, with a mixture of the three colors producing black. In practice, however, printing with only cyan, magenta, and yellow inks often does not produce the highest quality black, but instead results in a muddy brownish output due to impurities in the inks, the particular paper or other image recording media used, and the partial reflection of light instead of its complete absorption into the inks. Furthermore, select use of black ink in place of the primary colors reduces expense and minimizes the total amount of ink used which is often desirable in ink-jet and other printing applications where the ability of the recording substrate to absorb ink is limited.
Methods for converting from the CMY color space to the CMYK color space are commonly referred to as "undercolor removal" (UCR) and "grey-component replacement" (GCR). UCR/GCR methods vary, but commonly involve examining the individual pixels of an image using the lowest or "darkest" of the three cyan-magenta-yellow colors to determine an amount of black to be added (Undercolor Removal). One or more of the CMY colors are then adjusted to account for the addition of black ink (Grey Component Replacement). For example, if a given pixel of an image is represented in the CMY color space by C=0.5, M=0.4, and Y=0.25, then the black or K value would be based upon the lowest or Y value. In a 50% undercolor removal (UCR) method, K=50% of Y=0.125. In a typical grey component replacement (GCR) step, the remaining CMY values would then each be reduced by 0.125 so that the resulting UCR/GCR pixel is represented by C=0.375, M=0.275, Y=0.125, and K=0.125. Of course, other UCR/GCR methods are known, but each seeks to determine the level of black for a given pixel, and to thereafter adjust the other colors accordingly to account for the addition of black ink.
In the digital processing of color images, the individual color separations are conveniently represented as monochromatic bitmaps, which may be described as an electronic image with a plurality of discrete elements (hereinafter "pixels" ) defined by position and grey value. In such a system, grey value is described as one level in a number of possible states or levels. When more than two different levels are used in the description of an image, the levels are termed "grey" (without regard to the actual color) to indicate that the pixel value is between some maximum and minimum grey level. Most printing systems have the ability to reproduce an image with only a small number of grey values per pixel, most commonly two, although other numbers are possible. A printing system that is able to reproduce only two grey values for each pixel is said to produce binary output, i.e., the pixel is either "on" or "off."
On the other hand, image input devices, including digital cameras, scanners, and the like, are capable of describing each pixel of an image with many grey levels, for example 256 grey levels. Such input data is commonly called "continuous" or "contone" data. Accordingly, it is necessary that the input contone image (with many "grey" levels) be describable with the smaller set of grey levels reproducible by the output device in a manner that captures the intent of the user. In the digital reproduction of color images, this means that each of the color separations of the color-space must be reduced from the large number of continuous grey levels as input, to the smaller number of levels suitable for output. The multiple color separations are then combined together for printing to yield the final color print.
Given that common image output devices are "binary"--i.e., produce either "on" or "off" pixels for each color separation, it is necessary to employ halftoning techniques for each color separation to achieve the desired color within each separation before the color separations are combined for printing. Through halftoning, grey value variation within a color separation is represented by controlling the number of pixels that are "on" within a discrete area or cell of the separation. In such cases, the human eye and brain interpret the controlled number of "on" pixels in a halftone cell as a "grey level," with greater numbers of "on" pixels in a given cell or area being interpreted as darker color. In theory, a human observer does not see the individual "on" and "off" pixels within a halftone cell, but instead sees an average amount of ink on paper. In practice, the effectiveness of halftoning methods varies.
"Error diffusion" is one commonly employed halftoning method and is taught in "An Adaptive Algorithm for Spatial Greyscale" by Floyd and Steinberg, Proceedings of the SID 17/2, 75-77 (1976). Numerous other error diffusion methods are known. For example, commonly assigned U.S. Pat. No. 5,565,994 to Eschbach describes an error diffusion method particularly suited for application to multiple separation color documents. The foregoing documents are expressly incorporated by reference herein for their teachings.
In typical error diffusion methods, the different color components of a color image are separated from each other and error diffusion is performed on each separation. The output for each pixel ("on" or "off") is determined by comparing each pixel to a threshold. Input pixels of a grey value greater than the threshold are set to "on" while input pixels of a grey value less than the threshold are set to "off." However, unlike other halftoning methods, the difference or "error" between the actual grey value of a pixel and the resulting binary "on" (1) or "off" (0) states is not discarded. Instead, it is propagated to adjacent pixels so that it may be accounted for or "recovered" at some point. Thus, for example, even though an adjacent pixel may have an actual input continuous tone grey value less than the threshold, if an error from one or more previous pixels is added to the actual input value of the adjacent pixel, the adjacent pixel may thereafter exceed the threshold and be set to "on," thus recovering the previous error(s).
Heretofore, the foregoing digital color image processing techniques have been carried out without regard to each other. More particularly, the continuous-tone or "contone" CMY data was subjected to a UCR/GCR processing step as discussed above, and, thereafter, error diffusion was performed on each of the CMYK color separations. While such prior techniques are somewhat satisfactory, they are suboptimal in many instances and image quality varies with particular printing conditions. By way of another example, a uniform black region of an image is represented by each pixel having C=M=Y=1 before UCR/GCR. After a 50% UCR/GCR method is applied to each pixel, C=M=Y=K=0.5. If, as is done with prior techniques, error diffusion is then performed on each of the CMYK separations independently, each of the separations will have 1/2 of the pixels "on" (i.e, set to 1) and the other 1/2 off (i.e., set to 0). Under perfect or ideal printing conditions (perfect registration, square ink coverage, etc.), the desirable state will be C=M=Y=0 where K=1, and C=M=Y=1 where K=0. In other words, half of the pixels in the printed uniform black region will be covered by true black ink, and the other half of the pixels will be covered by equal amounts of CMY inks which also appears black. This produces an almost uniform black output.
However, as error diffusion results depend upon image boundary conditions, such uniform black output will rarely, if ever, occur. In a particular undesirable circumstance, where all four of the color separations are subjected to the same error diffusion, for example, the resulting printed image will be comprised of half the pixels covered by a combination of all four CMYK inks (C=M=Y=K=1) and the other half of the pixels being left blank (C=M=Y=K=0). Obviously, such printed output would not appear as the desired uniform black region. Other boundary conditions result in even less desirable printed output--e.g., noisy patches within the final printed image. Prior attempts to overcome these difficulties, such as working in density have somewhat alleviated the problem, but result in use of more ink and greater ink coverage, which is expensive, and not desirable for inkjet and other printing methods.
Accordingly, it is deemed desirable to develop a digital color imaging processing method that interrelates UCR/GCR techniques and error diffusion techniques that results in printed output wherein CMY and K pixels are uniformly distributed throughout the image and that prevents undesirable printing of color CMY inks and black K ink at the same location.